// https://leetcode.cn/problems/powx-n/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    double quickPow(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }

        double num = quickPow(x, n / 2);
        return n % 2 == 0 ? num * num : num * num * x;
    }
    double myPow(double x, int n) {
        long long N = n;
        if (n >= 0) {
            return quickPow(x, N);
        } else {
            return 1.0 / quickPow(x, -N);
        }
    }
};